package BinaryTree;

import java.util.*;

public class MyBinaryTree {
    public static class TreeNode {
        public char val;
        public TreeNode left;
        public TreeNode right;

        public TreeNode(char val) {
            this.val = val;
        }

    }

    public TreeNode createTree() {
        TreeNode A = new TreeNode('A');
        TreeNode B = new TreeNode('B');
        TreeNode C = new TreeNode('C');
        TreeNode D = new TreeNode('D');
        TreeNode E = new TreeNode('E');
        TreeNode F = new TreeNode('F');
        TreeNode G = new TreeNode('G');
        TreeNode H = new TreeNode('H');
        A.left = B;
        A.right = C;
        B.left = D;
        B.right = E;
        C.left = F;
        C.right = G;
        D.left = H;
        return A;
    }

    public TreeNode createTree1() {
        TreeNode A = new TreeNode('A');
        TreeNode B = new TreeNode('B');
        TreeNode C = new TreeNode('C');
        TreeNode D = new TreeNode('D');
        TreeNode E = new TreeNode('E');
        TreeNode F = new TreeNode('F');
        TreeNode G = new TreeNode('G');
        TreeNode H = new TreeNode('H');
        A.left = B;
        A.right = C;
        B.left = D;
        B.right = E;
        C.left = F;
        C.right = G;
        D.left = H;
        return A;
    }

    // 前序遍历
    public void PreTraversal(TreeNode root) {
        if (root == null) {
            return;
        }
        System.out.print(root.val + " ");
        PreTraversal(root.left);
        PreTraversal(root.right);
    }

    // 中序遍历
    public void MidTraversal(TreeNode root) {
        if (root == null) {
            return;
        }
        MidTraversal(root.left);
        System.out.print(root.val + " ");
        MidTraversal(root.right);
    }

    // 后序遍历
    public void LastTraversal(TreeNode root) {
        if (root == null) {
            return;
        }
        LastTraversal(root.left);
        LastTraversal(root.right);
        System.out.print(root.val + " ");
    }

    // 求所有的节点个数
    public int AllTreeNode(TreeNode root) {
        if (root == null) {
            return 0;
        }
        // 所有节点即为左树和右树节点之和加上根的节点
        return AllTreeNode(root.left) + AllTreeNode(root.right) + 1;
    }

    // 用临时变量来求所有节点个数
    public int size;

    public void leafTreeNode(TreeNode root) {
        if (root == null) {
            return;
        }
        if (root.left == null && root.right == null) {
            size++;
        }
        leafTreeNode(root.left);
        leafTreeNode(root.right);
    }

    // 求所有的叶子结点个数
    public int leafTreeNode1(TreeNode root) {
        if (root == null) {
            return 0;
        }
        if (root.left == null && root.right == null) {
            return 1;
        }
        return leafTreeNode1(root.left) + leafTreeNode1(root.right);
    }

    // 获取第k层的节点个数
    int temp;

    public int GetkTreeNode(TreeNode root, int k) {
        if (root == null) {
            return 0;
        }
        if (k == 1) {
            return 1;
        }
        return temp = GetkTreeNode(root.left, k - 1) + GetkTreeNode(root.right, k - 1);
    }

    // 求二叉树的高度
    public int GetHeight(TreeNode root) {
        if (root == null) {
            return 0;
        }
        int LeftHeight = GetHeight(root.left);
        int RightHeight = GetHeight(root.right);
        return Math.max(LeftHeight, RightHeight) + 1;
    }

    // 判断两个二叉树是否相同
    public boolean SameTree(TreeNode root1, TreeNode root2) {
        if (root1 == null && root2 != null || root1 != null && root2 == null) {
            return false;
        }
        if (root1 == null || root2 == null) {
            return true;
        }
        if (root1.val != root2.val) {
            return false;
        }
        boolean s1 = SameTree(root1.left, root2.left);
        boolean s2 = SameTree(root1.right, root2.right);
        return s1 && s2;
    }

    // 查找二叉树中的某个元素
    public TreeNode find(TreeNode root, char a) {
        if (root == null) {
            return null;
        }
        if (root.val == a) {
            return root;
        }
        TreeNode left = find(root.left, a);
        if (left != null) {
            if (left.val == a) {
                return left;
            }
        }
        TreeNode right = find(root.right, a);
        if (right != null) {
            if (right.val == a) {
                return right;
            }
        }
        return null;
    }

    // 翻转二叉树
    public TreeNode temp1;

    public TreeNode invertTree(TreeNode root) {
        if (root == null) {
            return null;
        }
        if (root.left == null && root.right == null) {
            return root;
        }
        if (root != null) {
            temp1 = root.left;
            root.left = root.right;
            root.right = temp1;
        }
        invertTree(root.left);
        invertTree(root.right);
        return root;
    }

    // 求二叉树是否是平衡二叉树
    // 一棵高度平衡二叉树定义为：一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1。
    public boolean isBalanced(TreeNode root) {
        if (root == null) {
            return true;
        }
        return GetHeight(root) >= 0;
    }

    public int GetHeight1(TreeNode root) {
        if (root == null) {
            return 0;
        }
        int LeftHeight = GetHeight1(root.left);
        if (LeftHeight < 0) {
            return -1;
        }
        int RightHeight = GetHeight1(root.right);
        if (Math.abs(LeftHeight - RightHeight) <= 1
                && LeftHeight >= 0 && RightHeight >= 0) {
            return Math.max(LeftHeight, RightHeight) + 1;
        } else {
            return -1;
        }
    }

    // 判断二叉树是否对称
    public boolean isSymmetric(TreeNode root) {
        if (root == null) {
            return true;
        }
        return isSymmetricChild(root.left, root.right);
    }

    public boolean isSymmetricChild(TreeNode leftTree, TreeNode rightTree) {
        if (leftTree == null && rightTree != null || leftTree != null && rightTree == null) {
            return false;
        }
        if (leftTree == null && rightTree == null) {
            return true;
        }
        if (leftTree.val != rightTree.val) {
            return false;
        }
        return isSymmetricChild(leftTree.left, rightTree.right) &&
                isSymmetricChild(leftTree.right, rightTree.left);
    }

    // 构建二叉树
    public int i = 0;

    public TreeNode CreateTree(String str) {
        TreeNode root = null;
        char ch = str.charAt(i);
        if (ch != '#') {
            root = new TreeNode(ch);
            i++;
            root.left = CreateTree(str);
            root.right = CreateTree(str);
        } else {
            i++;
        }
        return root;
    }

    // 二叉树的层序遍历
    public List<Character> LevelTraversal(TreeNode root) {
        Queue<TreeNode> queue = new LinkedList<>();
        List<Character> list = new ArrayList<>();
        if (root == null) {
            return list;
        }
        queue.offer(root);
        while (!queue.isEmpty()) {
            TreeNode car = queue.poll();
            list.add(car.val);
            if (car.left != null) {
                queue.offer(car.left);
            }
            if (car.right != null) {
                queue.offer(car.right);
            }
        }
        return list;
    }

    // 二叉树的层序遍历(用二维数组)
    public List<List<Character>> LevelTraversal1(TreeNode root) {
        List<List<Character>> lists = new ArrayList<>();
        if (root == null) {
            return lists;
        }
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        while (!queue.isEmpty()) {
            List<Character> list = new ArrayList<>();
            int size = queue.size();
            while (size != 0) {
                TreeNode car = queue.poll();
                list.add(car.val);
                size--;
                if (car.left != null) {
                    queue.offer(car.left);
                }
                if (car.right != null) {
                    queue.offer(car.right);
                }
            }
            lists.add(list);
        }
        return lists;
    }

    // 判断一棵树是否是完全二叉树
    public boolean isCompleteTree(TreeNode root) {
        Queue<TreeNode> queue = new LinkedList<>();
        if (root == null) {
            return true;
        }
        queue.offer(root);
        while (!queue.isEmpty()) {
            TreeNode car = root = queue.poll();
            if (car != null) {
                queue.offer(car.left);
                queue.offer(car.right);
            } else {
                break;
            }
        }
        while (!queue.isEmpty()) {
            if (queue.poll() != null) {
                return false;
            }
        }
        return true;
    }

    // 给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if (root == null) {
            return null;
        }
        if (root == p || root == q) {
            return root;
        }
        TreeNode left = lowestCommonAncestor(root.left, p, q);
        TreeNode right = lowestCommonAncestor(root.right, p, q);
        if (left != null && right != null) {
            return right;
        }
        if (left == null) {
            return right;
        } else {
            return left;
        }
    }

    public boolean getPath(TreeNode root, TreeNode node, Stack<TreeNode> stack) {
        if (root == null) {
            return false;
        }
        stack.push(root);
        if (root == node) {
            return true;
        }
        boolean flg1 = getPath(root.left, node, stack);
        if (flg1) {
            return true;
        }
        boolean flg2 = getPath(root.right, node, stack);
        if (flg2) {
            return true;
        }
        stack.pop();
        return false;
    }

    // 给定一个二叉树, 找到该树中两个指定节点的最近公共祖先(使用两个栈来进行寻找)。
    public TreeNode lowestCommonAncestor1(TreeNode root, TreeNode p, TreeNode q) {
        Stack<TreeNode> stack = new Stack<>();
        Stack<TreeNode> stack1 = new Stack<>();
        if (root == null) {
            return null;
        }
        getPath(root, p, stack);
        getPath(root, q, stack1);
        int size1 = stack.size();
        int size2 = stack1.size();
        int len = Math.abs(size1 - size2);
        if (size1 - size2 > 0) {
            while (len != 0) {
                stack.pop();
                len--;
            }
        } else {
            while (len != 0) {
                stack1.pop();
                len--;
            }
        }
        while (!stack.isEmpty() && !stack1.isEmpty()) {
            if (stack1.peek() == stack.peek()) {
                return stack.peek();
            } else {
                stack.pop();
                stack1.pop();
            }
        }
        return null;
    }

    // 用前序和中序遍历序列构造二叉树
    public TreeNode buildTree(char[] preorder, char[] inorder) {
        return buildTreeChild(preorder, inorder, 0, inorder.length - 1);
    }

    public int preIndex;

    public TreeNode buildTreeChild(char[] preorder, char[] inorder, int begin, int end) {
        if (begin > end) {
            return null;
        }
        TreeNode root = new TreeNode(preorder[preIndex]);
        int rootIndex = FindBuildTreeChild(inorder, begin, end, preorder[preIndex]);
        preIndex++;
        root.left = buildTreeChild(preorder, inorder, begin, rootIndex - 1);
        root.right = buildTreeChild(preorder, inorder, rootIndex + 1, end);
        return root;
    }

    public int FindBuildTreeChild(char[] inorder, int begin, int end, int key) {
        for (int i = begin; i <= end; i++) {
            if (inorder[i] == key) {
                return i;
            }
        }
        return -1;
    }

    // 用中序和后续遍历序列构造二叉树
    public int preIndex1;

    public TreeNode buildTree1(char[] inorder, char[] postorder) {
        preIndex1 = postorder.length - 1;
        return buildTreeChild1(postorder, inorder, 0, inorder.length - 1);
    }

    public TreeNode buildTreeChild1(char[] postorder, char[] inorder, int begin, int end) {
        if (begin > end) {
            return null;
        }
        TreeNode root = new TreeNode(postorder[preIndex1]);
        int rootIndex = FindBuildTreeChild1(inorder, begin, end, postorder[preIndex1]);
        preIndex1--;
        root.right = buildTreeChild1(postorder, inorder, rootIndex + 1, end);
        root.left = buildTreeChild1(postorder, inorder, begin, rootIndex - 1);
        return root;
    }

    public int FindBuildTreeChild1(char[] inorder, int begin, int end, int key) {
        for (int i = begin; i <= end; i++) {
            if (inorder[i] == key) {
                return i;
            }
        }
        return -1;
    }

    // 根据二叉树创建字符串
    public String tree2str(TreeNode root) {
        StringBuilder str = new StringBuilder();
        tree2strChild(root, str);
        return str.toString();
    }

    public void tree2strChild(TreeNode root, StringBuilder str) {
        if (root == null) {
            return;
        }
        str.append(root.val);
        if (root.left != null) {
            str.append("(");
            tree2strChild(root.left, str);
            str.append(")");
        } else {
            if (root.right != null) {
                str.append("()");
            }
        }
        if (root.right != null) {
            str.append("(");
            tree2strChild(root.right, str);
            str.append(")");
        } else {
            return;
        }
    }

    // 二叉树的前序遍历(使用非递归)
    public List<Character> preorderTraversal(TreeNode root) {
        List<Character> list = new ArrayList<>();
        Stack<TreeNode> stack = new Stack<>();
        if (root == null) {
            return list;
        }
        TreeNode car = root;
        while (car != null || !stack.isEmpty()) {
            while (car != null) {
                stack.push(car);
                list.add(car.val);
                car = car.left;
            }
            TreeNode top = stack.pop();
            car = top.right;
        }
        return list;
    }

    // 二叉树的中序遍历(使用非递归)
    public List<Character> inorderTraversal(TreeNode root) {
        List<Character> list = new ArrayList<>();
        Stack<TreeNode> stack = new Stack<>();
        if (root == null) {
            return list;
        }
        TreeNode car = root;
        TreeNode top = null;
        while (car != null || stack.isEmpty()) {
            while (car != null) {
                stack.push(car);
                car = car.left;
            }
            top = stack.pop();
            list.add(top.val);
            car = top.right;
        }
        return list;
    }

    // 二叉树的后序遍历(使用非递归)
    public List<Character> postorderTraversal(TreeNode root) {
        List<Character> list = new ArrayList<>();
        Stack<TreeNode> stack = new Stack<>();
        if (root == null) {
            return list;
        }
        TreeNode car = root;
        TreeNode top = null;
        TreeNode prev = null;
        while (car != null || !stack.isEmpty()) {
            while (car != null) {
                stack.push(car);
                car = car.left;
            }
            top = stack.peek();
            if (top.right == null || top.right == prev) {
                stack.pop();
                list.add(top.val);
                prev = top;
            } else {
                car = top.right;
            }
        }
        return list;
    }
}
